// https://www.lintcode.com/problem/605/my-submissions

class Solution {
public:
    /**
     * @param org: a permutation of the integers from 1 to n
     * @param seqs: a list of sequences
     * @return: true if it can be reconstructed only one or false
     */
    
    // 判断是否只有一个拓扑排序：队列中最多同时只有一个节点
   bool sequenceReconstruction(vector<int> &org, vector<vector<int>> &seqs) {
        unordered_map<int, multiset<int>> graph;
        unordered_map<int, int> degree;
        queue<int> q;
        vector<int> tp;
        
        for (auto seq: seqs) {
            if (seq.size() > 0 && degree.find(seq[0]) == degree.end()) {
                degree[seq[0]] = 0;
                graph[seq[0]];
            }
            for (int i = 1; i < seq.size(); ++i) {
                graph[seq[i]];
                if (graph[seq[i - 1]].find(seq[i]) == graph[seq[i - 1]].end()) { 
                    // !! 注意和图一致，要么图记录重复边，要么度矩阵里不记录重复
                    // vector<int> org = {4, 1, 5, 2, 6, 3};
                    // vector<vector<int>> seqs = {{5, 2, 6, 3}, {4, 1, 5, 2}};
                    degree[seq[i]] = degree[seq[i]] + 1;
                }
                graph[seq[i - 1]].insert(seq[i]);
            }
        }
        for (auto d: degree) {
            if (d.second == 0) {
                q.push(d.first);
                if (q.size() > 1) return false;
                tp.push_back(d.first);
            }
        }
        if (graph.size() == 0 && org.size() == 0) {
            return true;
        }
    
        if (graph.size() != org.size()) {
            return false;
        }

        while (!q.empty()) {
            int tmp = q.front();
            q.pop();
            for (auto next: graph[tmp]) {
                degree[next]--;
                if (degree[next] == 0) {
                    q.push(next);
                    if (q.size() > 1) return false;
                    tp.push_back(next);
                }
            }
        }
       
        return tp == org;
    }
};